#include "sort.h"
int partition(int arr[], int low, int high);
void bubbleSort(int *data, int len)
{
    //         for (size_t i = 0; i < len - 1; i++)
    //     {
    //         for (size_t j = i + 1; j < len; j++)
    //         {
    //             if (data[i] > data[j])
    //             {
    //                 int temp = data[i];
    //                 data[i] = data[j];
    //                 data[j] = temp;
    //             }
    //         }
    //     }
    for (size_t i = 0; i < len - 1; i++)
    {
        for (size_t j = 0; j < len - i - 1; j++)
        {
            if (data[j] > data[j + 1])
            {
                int temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
}
void chooseSort(int *data, int len)
{
    for (size_t i = 0; i < len - 1; i++)
    {
        int minIndex = i;
        for (size_t j = i + 1; j < len; j++)
        {
            if (data[minIndex] > data[j])
            {
                minIndex = j;
            }
        }
        int temp = data[minIndex];
        data[minIndex] = data[i];
        data[i] = temp;
    }
}
void insertSort1(int *data, int len)
{

    int i, j, key;
    for (size_t i = 1; i < len; i++)
    {
        int key = data[i];
        int j = i - 1;
        while (j >= 0 && data[j] > key)
        {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = key;
    }
}
void insertSort2(int *data, int len)
{
    int i, j, key;
    for (size_t i = 1; i < len; i++)
    {
        key = data[i];
        j = i - 1;
        while (j >= 0 && data[j] > key)
        {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = key;
    }
}
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        // pi 是分区后基准值的正确位置
        int pi = partition(arr, low, high);
        // 分别对基准值左右两边的子数组进行快速排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
int partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    while (low < high)
    {
        while (arr[low] <= pivot && low < high)
        {
            low++;
        }
        if (low < high)
        {
            arr[high--] = arr[low];
        }

        while (arr[high] >= pivot && low < high)
        {
            high--;
        }
        if (low < high)
        {
            arr[low++] = arr[high];
        }
    }
    arr[low] = pivot;
    return low;
}
int searchVal(int *data, int val, int low, int high) {  
    if (low > high) {  
        return -1; // 如果没有找到，返回-1  
    }  
  
    int mid = low + (high - low) / 2; // 防止溢出  
  
    if (data[mid] == val) {  
        return mid; // 如果中间元素就是目标值，直接返回  
    }  
  
    // 判断哪边是有序的  
    if (data[low] <= data[mid]) { // 左边有序  
        if (val >= data[low] && val < data[mid]) {  
            // 如果目标值在左半边有序区间内，则继续在左半边查找  
            return searchVal(data, val, low, mid - 1);  
        } else {  
            // 否则，在右半边查找  
            return searchVal(data, val, mid + 1, high);  
        }  
    } else { // 右边有序  
        if (val > data[mid] && val <= data[high]) {  
            // 如果目标值在右半边有序区间内，则继续在右半边查找  
            return searchVal(data, val, mid + 1, high);  
        } else {  
            // 否则，在左半边查找  
            return searchVal(data, val, low, mid - 1);  
        }  
    }  
}
void showArry(int *data, int len)
{
    for (size_t i = 0; i < len; i++)
    {
        printf("%d ", data[i]);
    }
    puts("");
}